package com.review.dp;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;

public class LC_120 {
    public static int minimumTotal(List<List<Integer>> triangle) {
        // 将list中的数据存入到数组中
        int a = triangle.size();
        int b = triangle.get(a - 1).size();
        int[][] nums = new int[a][b];
        int tmp = 0;
        for (List<Integer> integers : triangle) {
            for (int i = 0; i < integers.size(); i++) {
                nums[tmp][i] = integers.get(i);
            }
            tmp++;
        }
        // 将数组中的数据进行重新填充
        for (int i = 1; i < a; i++) {
            // 左侧数据
            nums[i][0] += nums[i - 1][0];
            // 右侧数据
            nums[i][i] += nums[i - 1][i - 1];
            // 中间数据填充
            for (int j = 1; j < i; j++) {
                nums[i][j] += Math.min(nums[i - 1][j], nums[i - 1][j - 1]);
            }
        }
        // 遍历数组最后一层得到最小值
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < b; i++) {
            min = Math.min(min, nums[a - 1][i]);
        }
        return min;
    }

    public static void main(String[] args) {
        List<Integer> list1 = Collections.singletonList(2);
        List<Integer> list2 = Arrays.asList(3, 4);
        List<Integer> list3 = Arrays.asList(6, 5, 7);
        List<Integer> list4 = Arrays.asList(4, 1, 8, 3);

        List<List<Integer>> lists = Arrays.asList(list1, list2, list3, list4);
        System.out.println(minimumTotal(lists));
    }
}
